#include <stdio.h>
#include <stdlib.h>


//题目:
//一个由1～N的数组中缺少了两个数字
//找出缺少的数字并打印
//控制时间复杂度为O(N)

//思路:
//将两个数组中的数全部异或(^)相同的数字均抵消

//柔性数组
typedef struct Flex {
    int N;
    int Arr[0];
}Flex;

//返回一组结果
typedef struct Ret {
    int ret1;
    int ret0;
}Ret;

Ret FindNull (int *arr, int N) {

    ////消失的两个数异或的结果
    int ret = N ^ (N - 1);
    for (int i = 1; i < N - 1; i++) {
        ret ^= arr[i - 1]; //与数组异或
        ret ^= i;       //与有序数列异或
    }

    //找到两个数异或为1的某一位
    int mov = 0;       //向右移动的位数
    for (int i = 0; i < 32; i++) {
        if ((ret >> i) & 1) {
            mov = i;
            break;
        }
    }

    //分离1和0为两组数
    int ret1 = 0;
    int ret0 = 0;
    for (int i = 0; i < N - 2; i++) {   //异或数组
        if ((arr[i] >> mov) & 1) {      //某位为1
            ret1 ^= arr[i];
        } else {                        //某位为0
            ret0 ^= arr[i];
        }
    }
    for (int i = 1; i <= N; i++) {      //异或数列
        if ((i >> mov) & 1) {           //某位为1
            ret1 ^= i;
        } else {                        //某位为0
            ret0 ^= i;
        }
    }

    //返回结果
    Ret result = {ret1, ret0};
    return result;
}

int main() {

    int N = 0;
    printf("请输入数据:");
    scanf("%d", &N);
    //创建柔数
    Flex *arr = (Flex *) malloc(sizeof(Flex) + sizeof(int) * (N - 2));
    if (arr == NULL) {
        perror("堆区动态内存开辟失败:");
    }
    arr->N = N - 2;

    //柔数使用
    printf("请出入数组:>");
    for (int i = 0; i < arr->N; i++) {
        scanf("%d", &arr->Arr[i]);
    }

    //调用函数
    Ret ret = FindNull(arr->Arr, N);

    printf("%d %d\n", ret.ret1, ret.ret0);

    //释放柔数
    free(arr);
    arr = NULL;
    return 0;
}